package day13;

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.locks.StampedLock;

/**
 * @author ZJX
 * @version 1.0
 * @descption 快速排序
 * @since 2025/10/22 23:18
 */
public class QuickSort {

    private final StampedLock stampedLock = new StampedLock(); // 乐观读 适合读多写少
    private final ConcurrentHashMap concurrentHashMap = new ConcurrentHashMap(); // 线程安全的hashmap
    private final CyclicBarrier cyclicBarrier = new CyclicBarrier(12);

    public static void quickSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        pitFillQuickSort(arr, 0, arr.length - 1);
    }

    public static void pitFillQuickSort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }

        int pivot = array[start];
        int left = start;
        int right = end;


        while (left < right) {
            while (left < right && array[right] >= pivot) {
                right--;
            }

            array[left] = array[right];
            while (left < right && array[left] <= pivot) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = pivot;

        pitFillQuickSort(array, start, left - 1);
        pitFillQuickSort(array, left + 1, end);
    }


    public int findKthLargest(int[] nums, int k) {
        int targetIndex = nums.length - k;
        return quickSelect(nums, 0, nums.length - 1, targetIndex);
    }

    private int quickSelect(int[] nums, int left, int right, int targetIndex) {
        if (left >= right) {
            return nums[left];
        }
        int pivot = nums[left];
        int l = left, r = right;
        while (r > l) {
            while (r > l && nums[r] >= pivot) {
                r--;
            }
            while (r > l && nums[l] <= pivot) {
                l++;
            }
            swap(nums, l, r);
        }
        swap(nums, l, left);
        int index = l;
        if (index == targetIndex) {
            return nums[index];
        } else if (index > targetIndex) {
            return quickSelect(nums, left, index - 1, targetIndex);
        } else {
            return quickSelect(nums, index + 1, right, targetIndex);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        // 测试用例
        int[] arr = {3, 2, 1, 5, 6, 4};
        quickSort(arr);
        for (int n : arr){
            System.out.print(n + " ");
        }
    }
}

